# Name: ...
# CSE 140
# Homework 4

import networkx as nx
import matplotlib.pyplot as plt
from operator import itemgetter
import random
import numpy as np

###
### Problem 1a
###

practice_graph = nx.Graph()

practice_graph.add_node("A")
practice_graph.add_node("B")
practice_graph.add_node("C")
practice_graph.add_node("D")
practice_graph.add_node("E")
practice_graph.add_node("F")

# TODO: Add more here...

practice_graph.add_edge("A", "B")
practice_graph.add_edge("A", "C")
practice_graph.add_edge("B", "C")
# TODO: Add more here...
practice_graph.add_edge("B", "D")
practice_graph.add_edge("C", "D")
practice_graph.add_edge("C", "F")
practice_graph.add_edge("D", "F")
practice_graph.add_edge("E", "D")

# 判断一下是否有误
assert len(practice_graph.nodes()) == 6
assert len(practice_graph.edges()) == 8


def draw_practice_graph():
    """Draw practice_graph to the screen."""
    nx.draw(practice_graph)
    plt.show()


# Comment out this line after you have visually verified your practice graph.
# Otherwise, the picture will pop up every time that you run your program.
# draw_practice_graph()


###
### Problem 1b
###
rj = nx.Graph()

rj.add_node("Nurse")  # A
rj.add_node("Juliet")  # b
rj.add_node("Tybalt")  # c
rj.add_node("Capulet")  # D
rj.add_node("Friar Laurence")  # E
rj.add_node("Romeo")  # F
rj.add_node("Benvolio")  # G
rj.add_node("Montague")  # H
rj.add_node("Escalus")  # I
rj.add_node("Mercutio")  # J
rj.add_node("Paris")  # K

rj.add_edge("Nurse", "Juliet")
rj.add_edge("Juliet", "Tybalt")
rj.add_edge("Friar Laurence", "Juliet")
rj.add_edge("Romeo", "Juliet")
rj.add_edge("Capulet", "Juliet")
rj.add_edge("Tybalt", "Capulet")
rj.add_edge("Capulet", "Escalus")
rj.add_edge("Capulet", "Paris")
rj.add_edge("Friar Laurence", "Romeo")
rj.add_edge("Romeo", "Benvolio")
rj.add_edge("Romeo", "Montague")
rj.add_edge("Romeo", "Mercutio")
rj.add_edge("Benvolio", "Montague")
rj.add_edge("Montague", "Escalus")
rj.add_edge("Paris", "Mercutio")
rj.add_edge("Escalus", "Mercutio")
rj.add_edge("Paris", "Escalus")

# (Your code goes here.)

assert len(rj.nodes()) == 11
assert len(rj.edges()) == 17


def draw_rj():
    """Draw the rj graph to the screen and to a file."""
    nx.draw(rj)
    plt.savefig("romeo-and-juliet.pdf")
    plt.show()


# Comment out this line after you have visually verified your rj graph and
# created your PDF file.
# Otherwise, the picture will pop up every time that you run your program.
# draw_rj()


###
### Problem 2
###

def friends(graph, user):
    """Returns a set of the friends of the given user, in the given graph.
    The parameter 'user' is the string name of a person in the graph.
    """
    return set(graph.neighbors(user))


def friends_of_friends(graph, user):
    """Returns a set of friends of friends of the given user, in the given graph.
    The result does not include the given user nor any of that user's friends.
    """
    test_set = set()
    for i in friends(graph, user):
        for j in friends(graph, i):
            if j != user and j not in friends(graph, user):
                test_set.add(j)
    return test_set

'''    for every in iter(friends_set):
        friends_of_friends_set=set()
        friends_of_friends_set.add(friends(graph,every))

        # sum=set()
        # sum = sum|friends_of_friends_set
    for i in iter(friends_of_friends_set):
        print(i)
    # print("To be implemented")
    return friends_of_friends_set'''

assert friends_of_friends(rj, "Mercutio") == set(['Benvolio', 'Capulet', 'Friar Laurence', 'Juliet', 'Montague'])


def common_friends(graph, user1, user2):
    """Returns the set of friends that user1 and user2 have in common."""
    common_friends_set = set(friends(graph, user1)).intersection(friends(graph, user2))
    return common_friends_set


assert common_friends(practice_graph, "A", "B") == set(['C'])
assert common_friends(practice_graph, "A", "D") == set(['B', 'C'])
assert common_friends(practice_graph, "A", "E") == set([])
assert common_friends(practice_graph, "A", "F") == set(['C'])

assert common_friends(rj, "Mercutio", "Nurse") == set()
assert common_friends(rj, "Mercutio", "Romeo") == set()
assert common_friends(rj, "Mercutio", "Juliet") == set(["Romeo"])
assert common_friends(rj, "Mercutio", "Capulet") == set(["Escalus", "Paris"])


def number_of_common_friends_map(graph, user):
    """Returns a map from each user U to the number of friends U has in common with the given user.
    The map keys are the users who have at least one friend in common with the
    given user, and are neither the given user nor one of the given user's friends.
    Take a graph G for example:
        - A and B have two friends in common
        - A and C have one friend in common
        - A and D have one friend in common
        - A and E have no friends in common
        - A is friends with D,所以说有两个键
    number_of_common_friends_map(G, "A")  =>   { 'B':2, 'C':1}
    """

    # M= graph.nodes - friends(graph, user)
    # values_cnt = {}
    # for every in M:
    #         if every!=user:
    #             if friends(graph,every)==friends(graph, user):
    #                 # values_cnt[every]+=1
    #                 values_cnt[every]=M.get(every,0)+1
    #             for i in values_cnt:
    #                  print(i)
    #             print("To be implemented")
    #         else:
    #             print("11111111")
    #             continue
    values_cnt = {}
    for every in friends_of_friends(graph, user):
        values_cnt[every] = len(friends(graph, every) & friends(graph, user))
    return values_cnt
assert number_of_common_friends_map(practice_graph, "A") == {'D': 2, 'F': 1}

assert number_of_common_friends_map(rj, "Mercutio") == {'Benvolio': 1, 'Capulet': 2, 'Friar Laurence': 1, 'Juliet': 1,
                                                        'Montague': 2}


def number_map_to_sorted_list(map):
    """Given a map whose values are numbers, return a list of the keys.
    The keys are sorted by the number they map to, from greatest to least.
    When two keys map to the same number, the keys are sorted by their
    natural sort order, from least to greatest."""
    # print ("To be implemented")
    # lt.sort(key=lambda x: x[1], reverse=True)  # 按照第二个元素的大小进行排序
    # lt = list(d.items())
    # lt=list(map.items())
    # m=lt.sort(key=lambda x: x[1], reverse=True)
    # print(m)
    # lt=sorted(map.items(), key=lambda map:map[1],reverse=True)
    lt = sorted(map.items(), key=lambda map: map[0])
    lt = sorted(lt, key=lambda map: map[1], reverse=True)
    res = [x[0] for x in lt]
    return res
    # lt=sorted(map,reverse=True)
    # sorted(map,key=lambda x: x[1].__getitem__, reverse=True)


# >>> students = ['dave', 'john', 'jane']
# >>> grades = {'john': 'F', 'jane':'A', 'dave': 'C'}
# >>> sorted(students, key=grades.__getitem__)
# ['jane', 'dave', 'john']


assert number_map_to_sorted_list({"a": 5, "b": 2, "c": 7, "d": 5, "e": 5}) == ['c', 'a', 'd', 'e', 'b']


def recommend_by_number_of_common_friends(graph, user):
    """Return a list of friend recommendations for the given user.
    The friend recommendation list consists of names of people in the graph
    who are not yet a friend of the given user.
    The order of the list is determined by the number of common friends.
    """
    map = number_of_common_friends_map(graph, user)
    dir = number_map_to_sorted_list(map)
    return dir
assert recommend_by_number_of_common_friends(practice_graph,"A") == ['D', 'F']
assert recommend_by_number_of_common_friends(rj, "Mercutio") == ['Capulet', 'Montague', 'Benvolio', 'Friar Laurence', 'Juliet']


###
### Problem 3
###

def influence_map(graph, user):
    """Returns a map from each user U to the friend influence, with respect to the given user.
    The map only contains users who have at least one friend in common with U,
    and are neither U nor one of U's friends.
    See the assignment for the definition of friend influence.
    """
    valuse_cnt = {}
    for every in friends(graph, user):
        for i in friends(graph, every) & friends_of_friends(graph, user):
            num1 = len(friends(graph, every))
            chance1 = 1 / num1  # 概率
            if i in valuse_cnt.keys():
                valuse_cnt[i] += chance1
            else:
                valuse_cnt[i] = chance1
    return valuse_cnt


assert influence_map(rj, "Mercutio") == {'Benvolio': 0.2, 'Capulet': 0.5833333333333333, 'Friar Laurence': 0.2,
                                         'Juliet': 0.2, 'Montague': 0.45}


def recommend_by_influence(graph, user):
    """Return a list of friend recommendations for the given user.
    The friend recommendation list consists of names of people in the graph
    who are not yet a friend of the given user.
    The order of the list is determined by the influence measurement.
    """
    map = influence_map(graph, user)
    recommend_by_influence_list = number_map_to_sorted_list(map)
    return recommend_by_influence_list
assert recommend_by_influence(rj, "Mercutio") == ['Capulet', 'Montague', 'Benvolio', 'Friar Laurence', 'Juliet']

###
### Problem 4
###
def Find_Different_Same (graph):
    Unchanged_recommendations=[]
    Changed_recommendations=[]
    for i in graph:
        if recommend_by_number_of_common_friends(graph, i)==recommend_by_influence(graph, i):
            Unchanged_recommendations.append(i)
        else:
            Changed_recommendations.append(i)
    print(Changed_recommendations)
    print(Unchanged_recommendations)


def Test_advantages_and_disadvantages(graph):
    friendship3=[]
    num1=0;num2=0;rank1=0;rank2=0
    for i in graph:
        s=[i]
        friendship1=friends(graph,i)
        for j in friendship1:
            friendship2=s.copy()
            friendship2.append(j)
            friendship3.append(friendship2)#frientship3是我们最后要的
    # friendship3=graph.edges
# **********************************************************************************************************************************
    for i in range(10):
        Sever_relations=random.choice(friendship3)
        graph.remove_edge(Sever_relations[0],Sever_relations[1])
        print(Sever_relations)
        # 断绝关系
        Recommended_method1_1=recommend_by_number_of_common_friends(graph,Sever_relations[0])
        Recommended_method1_2=recommend_by_number_of_common_friends(graph,Sever_relations[1])

        if Sever_relations[0] in Recommended_method1_2 and Sever_relations[1] in Recommended_method1_1:
            num1=num1+2
            rank1=rank1+Recommended_method1_2.index(Sever_relations[0])+Recommended_method1_1.index(Sever_relations[1])#第一个元素在第二个元素中的排名
            print(rank1)
        Recommended_method2_1=recommend_by_influence(graph,Sever_relations[0])
        Recommended_method2_2=recommend_by_influence(graph,Sever_relations[1])
        print(Recommended_method2_1)
        print(Recommended_method2_2)
        if Sever_relations[0] in Recommended_method2_2  and Sever_relations[1] in Recommended_method2_1:
                num2 = num2 + 2
                rank2 = rank2 + Recommended_method2_2.index(Sever_relations[0]) +Recommended_method2_1.index(Sever_relations[1])+ 2  # 第一个元素在第二个元素中的排名
        Average_ranking1 =rank1/num1#方法一
        Average_ranking2 =rank2/num2#方法一
        print("Average rank of influence method:",Average_ranking1)
        print("Average rank of number of friends in common method:",   Average_ranking2)
        if Average_ranking1>Average_ranking2:
            print( "Average rank of number of friends in common method is better")
        if Average_ranking1<Average_ranking2:
            print("Average rank of influence method is better")
        return 1

Test_advantages_and_disadvantages(rj)
###
### Problem 5
###

# (There is no code to write for this problem.)


###
### Problem 6
###

# (There is no code to write for this problem.)


###
### Problem 7
###
# ************************************************

###
### Problem 8
###
#图
facebook = nx.Graph()
def Get_number_of_rows():
    f = open("jia.txt")
    file = f.read()
    f.close()
    print(type(file))
    a = file.split()
    # length = len(a)
    return a
def Get_the_number_of_IDS():
    a=Get_number_of_rows()
    for i in range(len(a)-1,1,-3):
        a.pop(i)
    b=set(a)
    return b

def Create_a_Facebook_chart():
    b=Get_the_number_of_IDS()
    a=Get_number_of_rows()
    for i in range(len(b)):
        facebook.add_node(b.pop())
#获取行数
    count = -1
    for count, line in enumerate(open(r"jia.txt", 'rU')):
        count += 1
    # print(count)
    for i in range(count):
        facebook.add_edge(a[2*i], a[2*i+1])
    nx.draw(facebook)
    plt.savefig("romeo-and-juliet.pdf")
    plt.show()

Create_a_Facebook_chart()
# facebook=Create_a_Facebook_chart()
# 显示图像


# (Your code goes here.)

# assert len(facebook.nodes()) == 63731
# assert len(facebook.edges()) == 817090
###
### Problem 9
###
def List_of_IDS():
    user = Get_the_number_of_IDS()
    user_list = list(user)
    User_list = user_list.sort()
    return User_list

def Number_of_Facebook_friends_recommended(graph):
    User_list=List_of_IDS()
    for i in range(0,Get_number_of_rows(),1000):
        recommend_friends=recommend_by_number_of_common_friends(graph, User_list[i])
        Some_recommended_friends=recommend_friends[:10]
    return Some_recommended_friends


def Recommend_to_Facebook_based_on_Influence(graph):
    User_list=List_of_IDS()
    for i in range(0,Get_number_of_rows(),1000):
        recommend_friends=recommend_by_influence(graph, User_list[i])
        Some_recommended_friends=recommend_friends[:10]
    return Some_recommended_friends




###
### Problem 10
###
def Find_Different_Same2(graph):
    User_list = List_of_IDS()
    for i in User_list[:63]:
        Unchanged_recommendations = []
        Changed_recommendations = []
        for i in graph:
            if recommend_by_number_of_common_friends(graph, i) == recommend_by_influence(graph, i):
                Unchanged_recommendations.append(i)
            else:
                Changed_recommendations.append(i)
        print("Same:",Changed_recommendations)
        print("different:",Unchanged_recommendations)
###
### Problem 11
###


###
### Problem 12
###
def Test_advantages_and_disadvantages_plus(graph):
    friendship3 = []
    num1=0; num2=0;rank1=0;rank2=0
    for i in graph:
        s=[i]
        friendship1=friends(graph,i)
        for j in friendship1:
            friendship2=s.copy()
            friendship2.append(j)
            friendship3.append(friendship2)#frientship3是我们最后要的

    # friendship3=graph.edges
    for i in range(3):
        Sever_relations=random.choice(friendship3)
        graph.remove_edge(Sever_relations[0],Sever_relations[1])
        # print(Sever_relations)
        # 断绝关系
        Recommended_method1_1=recommend_by_number_of_common_friends(graph,Sever_relations[0])
        Recommended_method1_2=recommend_by_number_of_common_friends(graph,Sever_relations[1])

        if Sever_relations[0] in Recommended_method1_2 and Sever_relations[1] in Recommended_method1_1:
            num1=num1+2
            rank1=rank1+Recommended_method1_2.index(Sever_relations[0])+Recommended_method1_1.index(Sever_relations[1])#第一个元素在第二个元素中的排名
            # print(rank1)
        Recommended_method2_1=recommend_by_influence(graph,Sever_relations[0])
        Recommended_method2_2=recommend_by_influence(graph,Sever_relations[1])
        # print(Recommended_method2_1)
        # print(Recommended_method2_2)
        if Sever_relations[0] in Recommended_method2_2  and Sever_relations[1] in Recommended_method2_1:
                num2 = num2 + 2
                rank2 = rank2 + Recommended_method2_2.index(Sever_relations[0]) +Recommended_method2_1.index(Sever_relations[1])+ 2  # 第一个元素在第二个元素中的排名
        Average_ranking1 =rank1/num1#方法一
        Average_ranking2 =rank2/num2#方法一
        print("Average rank of influence method:",Average_ranking1)
        print("Average rank of number of friends in common method:",   Average_ranking2)
        if Average_ranking1>Average_ranking2:
            print( "Average rank of number of friends in common method is better")
        if Average_ranking1<Average_ranking2:
            print("Average rank of influence method is better")
        if Average_ranking1==Average_ranking2:
            print("As good as ")
        return 0
Test_advantages_and_disadvantages_plus(facebook)